Working storage is used by data processing systems to include control blocks, buffers, data areas and state vectors associated with the operation of a computer system in its execution of application programs or other work. Working storage is assigned from a portion of the physical memory of the data processing system. Physical memory typically is the form of a semiconductor memory.
A data processing system can include one or more processors which share a single physical memory. Each of the processors will run a plurality of tasks that continually demand the allocation of working storage and later release the working storage allocated (deallocation).
When a data processing system is first initialized, a certain portion of memory is dedicated as working storage. This storage is then allocated and used for the process of dynamic storage allocation or memory management.
In conventional memory managers, the continued allocation and deallocation of storage blocks results in a fragmented effect such as illustrated in FIG. 1. A series of allocated storage blocks such as 103 or 105 are separated by free areas, free blocks or available blocks, for example 102 and 104. This arrangement results in a great degree of fragmentation and wasteful use of storage. Storage inefficiency can be divided into at least two types of fragmentation. Internal fragmentation results when the storage allocation algorithm allocates more storage then requested through the process of rounding up storage request through an arbitrary boundary. The end result is that the allocated segments including extra, un-need storage space which could be more effectively used elsewhere. External fragmentation occurs by alternating blocks of available and in use storage are created through the allocation and deallocation process. The available blocks scattered throughout the storage area may be too small to satisfy a request for working storage. However, in aggregate, they represent a significant loss of working storage capacity. Central processing unit (CPU) inefficiency results when the system must spend considerable time searching through lists of available storage for a storage block that will satisfy a request for working storage. Available working storage blocks are typically managed as a linked link list of addresses in memory by links 106. A global storage list will contain an entry for each working storage block available in the processing system. A header record points to the first available storage block in working storage. A linked list is developed with each available storage block pointing to a successive storage block with the last storage block containing an end of the list indicator. A major drawback to the allocation method based on linked lists of available storage locations is the amount of processor time required to search the list in order to find an available block. The search time may be considerable if each search begins at the beginning of the list and proceeds until an available block of the appropriate size is found. Because allocation of blocks starts at the beginning of free storage, the smaller fragments of storage tend to occur at the beginning of the list. Thus, it is because at each time storage is allocated, only the amount of storage requested is actually allocated with whatever excess is available in the current block being broken off into a smaller fragment. The small fragments tend to aggregate toward the front of the storage area.
The prior art systems may employ a technique known as "garbage collection" to recover the unused storage blocks. The garbage collection process attempts to detect all unused entries and return them to the free list so that they may be allocated as efficiently as possible. This garbage collection process may be run periodically. The disadvantage of this periodic garbage collection is the increased processor workload required to place all items back on the free list and then to rebuild fixed sized queues. Thus, the management of memory resources may include three basic operations: allocation, deallocation and consolidation. If the process of fragmentation would continue unchecked, eventually the memory is divided into many small blocks of memory and a computer is unable to satisfy allocation requests for memory portions larger than the largest fragment. Thus, a scheme for deallocation is required. Thus, specific special purpose memory managers have been proposed, but these special purpose memory managers have not been applicable to replace a general purpose memory manager.